package gaobo.singlelist;

import leetcode.list.AddTwoNumbers;

public class Test {
    //合并有序列表
    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode head1 ,
                                                      MySingleList.ListNode head2){
        MySingleList.ListNode newHead = new MySingleList.ListNode(-1);
        MySingleList.ListNode tmp = newHead;
        while (head1 != null && head2 != null){
            if (head1.val < head2.val){
                tmp.next = head1;
                head1 = head1.next;
            }else {
                tmp.next = head2;
                head2 = head2.next;
            }
            tmp = tmp.next;
        }
        if (head1 != null){
            tmp.next = head1;
        }
        if (head2 != null){
            tmp.next = head2;
        }
        return newHead.next;
    }
    //相交链表
    //输入两个链表，找到他们的第一个公共节点，没有返回null
    public static MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA, MySingleList.ListNode headB){
        MySingleList.ListNode pl = headA;//pl 永远指向 最长的链表
        MySingleList.ListNode ps = headB;//ps 永远指向 最短的链表

        int lenA = 0;
        while (pl != null){
            lenA++;
            pl = pl.next;
        }
        int lenB = 0;
        while (ps != null){
            lenB++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
        int len = lenA - lenB;
        if (len < 0 ){
            pl = headB;
            ps = headA;
            len = lenB - lenA;
            //pl永远指向最长的链表 ps永远指向最短的链表
        }
        //2.让最长的链表先走len步
        while (len != 0){
            pl = pl.next;
            len--;
        }
        //3.pl和ps 在相同的起始位置
        while (pl != ps){
            pl = pl.next;
            ps = ps.next;
        }
        //走到这里pl和ps相等了并未相交 pl == ps == null
        if (pl == null){
            return null;
        }
        return pl;
    }

    public static void createCut(MySingleList.ListNode headA,
                                 MySingleList.ListNode headB){
        headB.next.next = headA.next.next;
    }

    public static MySingleList.ListNode addTwoNumbers(MySingleList.ListNode l1, MySingleList.ListNode l2) {
        MySingleList.ListNode cur = new MySingleList.ListNode(0);
        MySingleList.ListNode res = cur;
        int a = 0;//表示进位
        while (l1 != null || l2 != null || a != 0 ){
            int sum = a;
            if (l1 != null){
                sum = sum + l1.val;
                l1 = l1.next;
            }
            if (l2 != null){
                sum = sum + l2.val;
                l2 = l2.next;
            }
            res.next = new MySingleList.ListNode(sum % 10);
            a = sum / 10;
            res = res.next;
        }
        return cur.next;
    }





    public static void main(String[] args) {
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addLast(12);
        mySingleList1.addLast(23);
        mySingleList1.addLast(34);
        mySingleList1.addLast(45);
        //mySingleList1.addLast(52);
//        mySingleList1.display();

        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addLast(25);
        mySingleList2.addLast(35);
        //mySingleList2.addLast(4);
        //mySingleList2.addLast(5);
//        mySingleList2.addLast(53);
    //   addTwoNumbers(mySingleList1,mySingleList2);

        MySingleList.ListNode ret = mergeTwoLists(mySingleList1.head,mySingleList2.head);
        mySingleList1.display(ret);

//         mySingleList2.display();
//
  //      MySingleList.ListNode newHead = mergeTwoLists(mySingleList1.head,mySingleList2.head);
        //mySingleList1.display(newHead);
//        createCut(mySingleList1.head,mySingleList2.head);
//        MySingleList.ListNode ret = getIntersectionNode(mySingleList1.head,mySingleList2.head);
//        System.out.println(ret.val);

    }

}
